﻿#region MIT
/*
Engine Of Evermore (http://code.google.com/p/engineofevermore/)
Copyright (c) 2008, 2009 Michael Woerister

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using EngineOfEvermore.Common;

namespace EngineOfEvermore.Scene.Visual
{
    enum RectangleContainerProxyType
    {
        BEGIN,
        END
    }

    class RectangleContainerXProxy : IComparable<RectangleContainerXProxy>
    {
        public RectangleContainerXProxy( RectangleBounded item, 
            RectangleContainerProxyType type,
            int flagIndex )
        {
            this.Item = item;
            this.Type = type;
            this.QueryKeyIndex = flagIndex;
        }

        public readonly RectangleBounded Item;
        public readonly RectangleContainerProxyType Type;
        public readonly int QueryKeyIndex;

        public float RefValue
        {
            get
            {
                return ( this.Type == RectangleContainerProxyType.BEGIN ) ?
                    this.Item.AABB.Left : this.Item.AABB.Right;
            }
        }

        public int CompareTo( RectangleContainerXProxy other )
        {
            float thisValue = this.RefValue;
            float otherValue = other.RefValue;

            return thisValue < otherValue ? -1 : ( thisValue > otherValue ? 1 : 0 );
        }
    }

    class RectangleContainerYProxy : IComparable<RectangleContainerYProxy>
    {
        public RectangleContainerYProxy( RectangleBounded item, 
            RectangleContainerProxyType type,
            int flagIndex )
        {
            this.Item = item;
            this.Type = type;
            this.QueryKeyIndex = flagIndex;
        }

        public readonly RectangleBounded Item;
        public readonly RectangleContainerProxyType Type;
        public readonly int QueryKeyIndex;

        public float RefValue
        {
            get
            {
                return ( this.Type == RectangleContainerProxyType.BEGIN ) ?
                    this.Item.AABB.Left : this.Item.AABB.Right;
            }
        }

        public int CompareTo( RectangleContainerYProxy other )
        {
            float thisValue = this.RefValue;
            float otherValue = other.RefValue;

            return thisValue < otherValue ? -1 : ( thisValue > otherValue ? 1 : 0 );
        }
    }

    /// <summary>
    /// A container that can hold objects of the type RectangleBounded.
    /// </summary>
    public class RectangleContainer : ISimpleSet<RectangleBounded>
    {
        #region Variables
        LinkedList<RectangleContainerXProxy> _xProxyList = 
            new LinkedList<RectangleContainerXProxy>();
        LinkedList<RectangleContainerYProxy> _yProxyList = 
            new LinkedList<RectangleContainerYProxy>();

        List<uint> _proxyQueryKeys = new List<uint>();
        List<int> _freeQueryKeyIndices = new List<int>();
        uint _queryKey;
        #endregion

        #region Constructor
        public RectangleContainer()
        {
            for ( int i = 0; i < 32; ++i )
            {
                _proxyQueryKeys.Add( 0 );
                _freeQueryKeyIndices.Add( i );
            }
        }
        #endregion

        #region Properties
        /// <summary>
        /// Returns the number of items contained in this collection.
        /// </summary>
        public int Count
        {
            get
            {
                Debug.Assert( _xProxyList.Count == _yProxyList.Count );
                Debug.Assert( _xProxyList.Count % 2 == 0 );

                return _xProxyList.Count / 2;
            }
        }
        #endregion

        #region Methods
        /// <summary>
        /// Adds an item to the container.
        /// </summary>
        /// <remarks>
        /// The item must not already be contained in this container.
        /// </remarks>
        public void Add( RectangleBounded item )
        {
            Debug.Assert( !_xProxyList.Any( proxy => proxy.Item == item ) );
            Debug.Assert( !_yProxyList.Any( proxy => proxy.Item == item ) );

            int flagIndex = _getQueryKeyIndex();

            RectangleContainerXProxy beginXProxy = 
                new RectangleContainerXProxy( item, 
                    RectangleContainerProxyType.BEGIN, 
                    flagIndex );

            RectangleContainerXProxy endXProxy = 
                new RectangleContainerXProxy( item, 
                    RectangleContainerProxyType.END, 
                    flagIndex );

            if ( _xProxyList.First != null )
            {
                LinkedListNode<RectangleContainerXProxy> it = _xProxyList.First;

                while ( it != null && it.Value.RefValue < beginXProxy.RefValue )
                {
                    it = it.Next;
                }

                if ( it != null )
                {
                    item.ContainerBeginXProxy = 
                        _xProxyList.AddBefore( it, beginXProxy );

                    while ( it != null && it.Value.RefValue < endXProxy.RefValue )
                    {
                        it = it.Next;
                    }

                    if ( it != null )
                    {
                        _xProxyList.AddBefore( it, endXProxy );
                    }
                    else
                    {
                        _xProxyList.AddLast( endXProxy );
                    }
                }
                else
                {
                    item.ContainerBeginXProxy = _xProxyList.AddLast( beginXProxy );
                    _xProxyList.AddLast( endXProxy );
                }
            }
            else
            {
                _xProxyList.AddFirst( endXProxy );
                item.ContainerBeginXProxy = _xProxyList.AddFirst( beginXProxy );
            }

            RectangleContainerYProxy beginYProxy = 
                new RectangleContainerYProxy( item, 
                    RectangleContainerProxyType.BEGIN,
                    flagIndex 
                    );

            RectangleContainerYProxy endYProxy = 
                new RectangleContainerYProxy( item, 
                    RectangleContainerProxyType.END, 
                    flagIndex );

            if ( _yProxyList.First != null )
            {
                LinkedListNode<RectangleContainerYProxy> it = _yProxyList.First;

                while ( it != null && it.Value.RefValue < beginYProxy.RefValue )
                {
                    it = it.Next;
                }

                if ( it != null )
                {
                    item.ContainerBeginYProxy = 
                        _yProxyList.AddBefore( it, beginYProxy );

                    while ( it != null && it.Value.RefValue < endYProxy.RefValue )
                    {
                        it = it.Next;
                    }

                    if ( it != null )
                    {
                        _yProxyList.AddBefore( it, endYProxy );
                    }
                    else
                    {
                        _yProxyList.AddLast( endYProxy );
                    }
                }
                else
                {
                    item.ContainerBeginYProxy = _yProxyList.AddLast( beginYProxy );
                    _yProxyList.AddLast( endYProxy );
                }
            }
            else
            {
                _yProxyList.AddFirst( endYProxy );
                item.ContainerBeginYProxy = _yProxyList.AddFirst( beginYProxy );
            }

            Debug.Assert( item.ContainerBeginXProxy.Value.Type == RectangleContainerProxyType.BEGIN );
            Debug.Assert( item.ContainerBeginYProxy.Value.Type == RectangleContainerProxyType.BEGIN );
        }


        /// <summary>
        /// Removes an item from the container.
        /// </summary>
        public void Remove( RectangleBounded item )
        {
            Debug.Assert( _xProxyList.Count( proxy => proxy.Item == item ) == 2 );
            Debug.Assert( _yProxyList.Count( proxy => proxy.Item == item ) == 2 );

            LinkedListNode<RectangleContainerXProxy> xIt = _xProxyList.First;

            while ( xIt != null )
            {
                if ( xIt.Value.Item == item )
                {
                    LinkedListNode<RectangleContainerXProxy> deletedNode = xIt;
                    xIt = xIt.Next;
                    _xProxyList.Remove( deletedNode );
                }
                else
                {
                    xIt = xIt.Next;
                }
            }

            LinkedListNode<RectangleContainerYProxy> yIt = _yProxyList.First;

            while ( yIt != null )
            {
                if ( yIt.Value.Item == item )
                {
                    LinkedListNode<RectangleContainerYProxy> deletedNode = yIt;
                    yIt = yIt.Next;
                    _yProxyList.Remove( deletedNode );
                }
                else
                {
                    yIt = yIt.Next;
                }
            }

            item.ContainerBeginXProxy = null;
            item.ContainerBeginYProxy = null;
        }

        /// <summary>
        /// Updates the container. 
        /// </summary>
        public void Update()
        {
            _xProxyList.InsertionSort();
            _yProxyList.InsertionSort();
        }

        /// <summary>
        /// Finds all overlaps between 'item' and all other items in the container.
        /// </summary>
        /// <param name="item">An item that itself must be contained in the container.</param>
        /// <param name="output">The collection all found items will be added to.</param>
        /// <remarks>
        /// This method will only yield correct results, if the AABBs of the contained objects 
        /// have not changed since the last call to RectangleContainer.Update().
        /// </remarks>
        public void FindOverlaps( RectangleBounded item, 
            ICollection<RectangleBounded> output )
        {
            Debug.Assert( _xProxyList.Count( proxy => proxy.Item == item ) == 2 );
            Debug.Assert( _yProxyList.Count( proxy => proxy.Item == item ) == 2 );
            
            ++_queryKey;
            
            LinkedListNode<RectangleContainerXProxy> xIt = item.ContainerBeginXProxy;
           
            //Debug.Assert( xIt.Previous == null || xIt.Previous.Value.RefValue < xIt.Value.RefValue );
            while ( xIt.Previous != null && xIt.Previous.Value.Type == RectangleContainerProxyType.BEGIN && 
                   xIt.Previous.Value.RefValue == xIt.Value.RefValue )
            {
                var prevNode = xIt.Previous;
                _xProxyList.Remove( xIt );
                _xProxyList.AddBefore( prevNode, xIt );
            }
                   
            xIt = xIt.Next;
            
            // Run to the end of the query item
            while ( xIt.Value.Item != item )
            {
                // Mark all query keys with the current key
                _proxyQueryKeys[xIt.Value.QueryKeyIndex] = _queryKey;
                xIt = xIt.Next;
            }
            
            // Now Run to the end of the list
            while ( xIt != null )
            {
                if ( xIt.Value.Type == RectangleContainerProxyType.END )
                {
                    if ( xIt.Value.Item.AABB.Left < item.AABB.Left )
                    {
                        _proxyQueryKeys[xIt.Value.QueryKeyIndex] = _queryKey;
                    }
                }
            
                xIt = xIt.Next;
            }
            
            LinkedListNode<RectangleContainerYProxy> yIt = item.ContainerBeginYProxy;

            //Debug.Assert( yIt.Previous == null || yIt.Previous.Value.RefValue < yIt.Value.RefValue );
            while ( yIt.Previous != null && yIt.Previous.Value.Type == RectangleContainerProxyType.BEGIN && 
                    yIt.Previous.Value.RefValue == yIt.Value.RefValue )
            {
                var prevNode = yIt.Previous;
                _yProxyList.Remove( yIt );
                _yProxyList.AddBefore( prevNode, yIt );
            } 
                   
            yIt = yIt.Next;
            
            // Run to the end of item
            while ( yIt.Value.Item != item )
            {
                // Is there already an interference on the x-axis?
                if ( _proxyQueryKeys[yIt.Value.QueryKeyIndex] == _queryKey )
                {
                    if ( yIt.Value.Type == RectangleContainerProxyType.BEGIN )
                    {
                        // This is a BEGIN-proxy -> interference
                        output.Add( yIt.Value.Item );
                    }
                    else
                    {
                        // This is an END-proxy, so we need to test if it was already added
                        if ( yIt.Value.Item.AABB.Left < item.AABB.Left )
                        {
                            output.Add( yIt.Value.Item );
                        }
                    }
                }
                
                yIt = yIt.Next;
            }
            
            // Now Run to the end of the list
            while ( yIt != null )
            {
                if ( yIt.Value.Type == RectangleContainerProxyType.END )
                {
                    if (  _proxyQueryKeys[yIt.Value.QueryKeyIndex] == _queryKey && yIt.Value.Item.AABB.Left < item.AABB.Left )
                    {
                        output.Add( yIt.Value.Item );
                    }
                }
            
                yIt = yIt.Next;
            }
        }

        public void Clear()
        {
            _xProxyList.Clear();
            _yProxyList.Clear();
        }

        public bool Contains( RectangleBounded item )
        {
            Debug.Assert( _xProxyList.Any( p => p.Item == item ) ==
                _yProxyList.Any( p => p.Item == item ) );

            return _xProxyList.Any( x => x.Item == item );
        }

        public IEnumerator<RectangleBounded> GetEnumerator()
        {
            EnumeratorEqualityComparer comparer = new EnumeratorEqualityComparer();
            return _xProxyList.Distinct( comparer ).Select( p => p.Item ).GetEnumerator();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
        #endregion

        #region Private Stuff
        int _getQueryKeyIndex()
        {
            if ( _freeQueryKeyIndices.Count == 0 )
            {
                int start = _proxyQueryKeys.Count;

                for ( int i = 0; i < 32; ++i )
                {
                    _proxyQueryKeys.Add( _queryKey );
                    _freeQueryKeyIndices.Add( start + i );
                }
            }

            int index = _freeQueryKeyIndices[_freeQueryKeyIndices.Count - 1];
            _freeQueryKeyIndices.RemoveAt( _freeQueryKeyIndices.Count - 1 );
            return index;
        }
        
        // This comparer is used in GetEnumerator.
        struct EnumeratorEqualityComparer : IEqualityComparer<RectangleContainerXProxy>
        {
            public bool Equals( RectangleContainerXProxy x, RectangleContainerXProxy y )
            {
                return x.QueryKeyIndex == y.QueryKeyIndex;
            }

            public int GetHashCode( RectangleContainerXProxy obj )
            {
                return obj.QueryKeyIndex;
            }
        }
        #endregion
    }
    
    #if ENGINE_OF_EVERMORE_ENABLE_UNIT_TESTS
    namespace Test
    {
        using System.Drawing;        
    	using NUnit.Framework;
    	
    	[TestFixture]
    	public class TestRectangleContainer
    	{
    	    class TestRectangleBounded : RectangleBounded
        	{    		
        		public new RectangleF AABB
        		{
        		    get { return _aabb; }
        		    set { _aabb = value; }
        		}
        	}
    	    
    		[Test]
    		public void TestAdd()
    		{
    			RectangleContainer rectcont = new RectangleContainer();
    			TestRectangleBounded rb = new TestRectangleBounded();
    			rb.AABB = new RectangleF( 1.0f, 1.0f, 3.0f, 4.0f );
    			rectcont.Add( rb );
    			
    			Assert.That( rectcont.Contains( rb ), Is.True );
    		}
    		
    		[Test]
    		public void TestRemove()
    		{
    			RectangleContainer rectcont = new RectangleContainer();
    			TestRectangleBounded rb1 = new TestRectangleBounded();
    			TestRectangleBounded rb2 = new TestRectangleBounded();
    			
    			rb1.AABB = new RectangleF( 1.0f, 1.0f, 3.0f, 4.0f );
    			rb2.AABB = new RectangleF( 2.0f, 2.0f, 3.0f, 4.0f );
    			
    			rectcont.Add( rb1 );
    			rectcont.Add( rb2 );
    			
    			rectcont.Remove( rb1 );
    			
    			Assert.That( rectcont.Contains( rb2 ), Is.True );
    			Assert.That( rectcont.Contains( rb1 ), Is.False );
    		}
    		
    		[Test]
    		public void TestUpdate()
    		{
    			RectangleContainer rectcont = new RectangleContainer();
    			TestRectangleBounded rb1 = new TestRectangleBounded();
    			TestRectangleBounded rb2 = new TestRectangleBounded();

    			rb1.AABB = new RectangleF( 1.0f, 1.0f, 3.0f, 4.0f );
    			rb2.AABB = new RectangleF( 2.0f, 2.0f, 3.0f, 4.0f );
    			
    			rectcont.Add( rb1 );
    			rectcont.Add( rb2 );
    			
    			rectcont.Update();
    			
    			Assert.That( rectcont.Contains( rb1 ), Is.True );
    			Assert.That( rectcont.Contains( rb2 ), Is.True );    		
    		}
    		
    		[Test]
    		public void TestFindOverlapsEqualBoundaryValues()
    		{
    			RectangleContainer rectcont = new RectangleContainer();
    			List<RectangleBounded> resultList = new List<RectangleBounded>();
    			List<RectangleBounded> expectedList = new List<RectangleBounded>();
    			
    			TestRectangleBounded rb1 = new TestRectangleBounded();
    			TestRectangleBounded rb2 = new TestRectangleBounded();
    			TestRectangleBounded rb3 = new TestRectangleBounded();
    			TestRectangleBounded rb4 = new TestRectangleBounded();

    			rb1.AABB = new RectangleF( 1.0f, 1.0f, 3.0f, 4.0f );
    			rb2.AABB = new RectangleF( 1.0f, 2.0f, 3.0f, 4.0f );
    			rb3.AABB = new RectangleF( 7.0f, 1.0f, 1.0f, 1.0f ); // alone
    			rb4.AABB = new RectangleF( 1.5f, 3.0f, 2.0f, 1.0f ); // overlapping with rect1 & rect2
    			
    			rectcont.Add( rb1 );
    			rectcont.Add( rb2 );
    			rectcont.Add( rb3 );
    			rectcont.Add( rb4 );
    			
    			rectcont.Update();
    			
    			expectedList.Add( rb1 );
    			expectedList.Add( rb2 );
    			
    			rectcont.FindOverlaps( rb4, resultList );
    			
    			Assert.That( resultList, Is.EquivalentTo( expectedList ) );
    		}
    		
    		[Test]
    		public void TestFindOverlaps()
    		{
    			RectangleContainer rectcont = new RectangleContainer();
    			List<RectangleBounded> resultList = new List<RectangleBounded>();
    			List<RectangleBounded> expectedList = new List<RectangleBounded>();
    			
    			TestRectangleBounded rb1 = new TestRectangleBounded();
    			TestRectangleBounded rb2 = new TestRectangleBounded();
    			TestRectangleBounded rb3 = new TestRectangleBounded();
    			TestRectangleBounded rb4 = new TestRectangleBounded();

    			rb1.AABB = new RectangleF( 1.0f, 1.0f, 3.0f, 4.0f );
    			rb2.AABB = new RectangleF( 2.0f, 2.0f, 3.0f, 4.0f );
    			rb3.AABB = new RectangleF( 7.0f, 1.0f, 1.0f, 1.0f ); // alone
    			rb4.AABB = new RectangleF( 1.5f, 3.0f, 2.0f, 1.0f ); // overlapping with rect1 & rect2
    			
    			rectcont.Add( rb1 );
    			rectcont.Add( rb2 );
    			rectcont.Add( rb3 );
    			rectcont.Add( rb4 );
    			
    			rectcont.Update();
    			
    			expectedList.Add( rb1 );
    			expectedList.Add( rb2 );
    			
    			rectcont.FindOverlaps( rb4, resultList );
    			
    			Assert.That(  resultList, Is.EquivalentTo( expectedList ) );
    		}
    		
    		[Test]
    		public void TestClear()
    		{
    			RectangleContainer rectcont = new RectangleContainer();
    			RectangleBounded rb1 = new RectangleBounded();
    			RectangleBounded rb2 = new RectangleBounded();
    			
    			rectcont.Add( rb1 );
    			rectcont.Add( rb2 );
    			
    			rectcont.Clear();
    			
    			Assert.That( rectcont.Contains( rb1 ), Is.False );
    			Assert.That( rectcont.Contains( rb2 ), Is.False );
    		}
    		
    		[Test]
    		public void TestCount()
    		{
    			RectangleContainer rectcont = new RectangleContainer();
    			TestRectangleBounded rb1 = new TestRectangleBounded();
    			TestRectangleBounded rb2 = new TestRectangleBounded();
    			
    			rb1.AABB = new RectangleF( 2.0f, 2.0f, 3.0f, 4.0f );
    			rb2.AABB = new RectangleF( 1.0f, 1.0f, 2.0f, 6.0f );
    			
    			rectcont.Add( rb1 );
    			rectcont.Add( rb2 );
    			
    			Assert.That( rectcont.Count, Is.EqualTo( 2 ) );
    		}
    		
    		[Test]
    		public void TestGetEnumerator()
    		{
    			RectangleContainer rectcont = new RectangleContainer();
    			RectangleContainer resultcont = new RectangleContainer();
    			TestRectangleBounded rb1 = new TestRectangleBounded();
    			TestRectangleBounded rb2 = new TestRectangleBounded();
    			
    			rb1.AABB = new RectangleF( 2.0f, 2.0f, 3.0f, 4.0f );
    			rb2.AABB = new RectangleF( 1.0f, 1.0f, 2.0f, 6.0f );
    			
    			rectcont.Add( rb1 );
    			rectcont.Add( rb2 );
    			
    			foreach( TestRectangleBounded rb in ( System.Collections.IEnumerable ) rectcont )
    			{
    				resultcont.Add( rb );
    			}
    			
    			Assert.That( resultcont.Contains( rb1 ), Is.True );
    			Assert.That( resultcont.Contains( rb2 ), Is.True );
    		}
    		
    		[Test]
    		public void TestAdd33Objects()
    		{
    			RectangleContainer rectcont = new RectangleContainer();
    			
    			for ( int i = 0; i < 33; i++ )
    			{
    				rectcont.Add( new TestRectangleBounded() );
    			}
    			
    			Assert.That( rectcont.Count, Is.EqualTo( 33 ) );
    		}
    		
    		[Test]
    		public void TestENDProxyOverlap()
    		{
    			RectangleContainer rectcont = new RectangleContainer();
    			TestRectangleBounded rb1 = new TestRectangleBounded();
    			TestRectangleBounded rb2 = new TestRectangleBounded();
    			TestRectangleBounded rb3 = new TestRectangleBounded();
    			List<RectangleBounded> resultList = new List<RectangleBounded>();
    			List<RectangleBounded> expectedList = new List<RectangleBounded>();
    			
    			rb1.AABB = new RectangleF( 1.0f, 1.0f, 2.0f, 3.0f );
    			rb2.AABB = new RectangleF( 2.0f, 1.0f, 2.0f, 3.0f );
    			rb3.AABB = new RectangleF( 7.0f, 1.0f, 1.0f, 1.0f ); // alone
    			
    			rectcont.Add( rb1 );
    			rectcont.Add( rb2 );
    			rectcont.Add( rb3 );
    			
    			expectedList.Add( rb1 );
    			
    			rectcont.FindOverlaps( rb2, resultList );
    			
    			Assert.That( resultList, Is.EquivalentTo( expectedList ) );
    		}
    		
    		[Test]
    		public void TestOverlapInYDirection() // sets "xIt.Previous.Value.RefValue == xIt.Value.RefValue" to TRUE
    		{
    			RectangleContainer rectcont = new RectangleContainer();
    			TestRectangleBounded rb1 = new TestRectangleBounded();
    			TestRectangleBounded rb2 = new TestRectangleBounded();
    			TestRectangleBounded rb3 = new TestRectangleBounded();
    			List<RectangleBounded> resultList = new List<RectangleBounded>();
    			List<RectangleBounded> expectedList = new List<RectangleBounded>();
    			
    			rb1.AABB = new RectangleF( 1.0f, 1.0f, 2.0f, 3.0f );
    			rb2.AABB = new RectangleF( 1.0f, 2.0f, 2.0f, 3.0f );
    			rb3.AABB = new RectangleF( 7.0f, 1.0f, 1.0f, 1.0f ); // alone
    			
    			rectcont.Add( rb1 );
    			rectcont.Add( rb2 );
    			rectcont.Add( rb3 );

    			expectedList.Add( rb2 );
    			
    			rectcont.FindOverlaps( rb1, resultList );
    			
    			Assert.That( resultList, Is.EquivalentTo( expectedList ) );
    		}
    	}
    }
    #endif
}
